package com.lizk.heap;

import com.lizk.sort.SortUtils;

/**
 * 索引从1开始的最小堆
 * 与最小堆相反,订单的值是节点中最小的值
 * @author lizhikui
 * @date 2020/2/9 14:47
 */
public class MinHeap<T extends Comparable<T>> {

    /**
     * 当前的存储数据的数量
     */
    private int size;
    /**
     * 存储数量的数据
     */
    private T [] value;

    /**
     * 构造函数，最小堆的索引从1开始
     * @param length  指定存储数据数组的长度
     */
    public MinHeap(int length){
        this.size  = 0;
        value = (T[])new Comparable [length + 1];
    }

    public MinHeap(T [] array){
        this.heapify(array);
    }

    /**
     * 插入一个元素
     * @param item  插入的数据
     */
    public void insertValue(T item){
        //如果数组已经满了，那么直接报错
        if (size + 1 >= value.length){
            throw new RuntimeException("数据已存满");
        }
        size ++;
        value[size] = item;
        //把插入的元素自底向上调整到合适的位置
        shiftUp();
    }

    public T takeValue(){
        T result =  value[1];
        value[1] = value[size];
        value[size] = null;
        size --;
        shiftDown(1);
        return result;
    }

    /**
     * 把完全没有顺序的完全二叉树，转换成最小堆
     * 思路：
     * 1.把每个最后的叶子结点看成是一个组织好的最小堆
     * 2.然后从最后一个非叶子结点开始，一次做shiftdown处理
     * 3.这里通过array直接构造一个堆的时间复杂度为n级别
     */
    public void heapify(T [] array){
        value = (T[])new Comparable[array.length + 1];
        size = array.length;
        for (int i = 0; i < array.length; i++) {
            value[i+1] = array[i];
        }

        for (int i = size/2 ; i >=1 ; i--){
            shiftDown(i);
        }
    }

    /**
     * 把最后一个不符合规则的元素，依次向上移动，直到合适的位置。
     */
    private void shiftUp(){
        //步长为2，所以时间复杂度为logn
        for (int i = size ; i > 1 ; i=i/2){
            //当前位置与父节点比较，如果父节点小，那么交换位置，循环处理的节点转到当前节点的父节点
            if(value[i].compareTo(value[i/2]) < 0 ){
                SortUtils.swap(value,i,i/2);
            }
        }
    }

    /**
     * 把最上面不符合规则的元素依次向下移动，直到合适的位置
     */
    private void shiftDown(int index){
        //每次长两个步长，所以整个算法的时间复杂度为logn级别的
        for (int i = index; i * 2 <= size;) {
            int tmp = i * 2;

            //比较两个子节点的大小,选出值小的那个节点的索引
            if (i*2+1 <= size && value[i * 2].compareTo(value[i*2+1]) > 0){
                tmp = i * 2 + 1;
            }

            //把当前值与较小的子节点的值进行比较,如果当前值大，那么就交换位置,把值小的子节点交换到父节点上来
            if (value[i].compareTo(value[tmp]) > 0){
                SortUtils.swap(value,i,tmp);
                i = tmp;
            }else {
                break;
            }
        }
    }

    /**
     * 计算指定索引元素所在的树的层次
     * @return
     */
    private int calcFloor(int index){
        double d = Math.log(index)/Math.log(2);
        int floor = (int)Math.ceil(d);
        return floor;
    }

    //打印树
    public void print(){
        //计算指定索引元素所在的树的层次
            /*double d = Math.log(size +1 )/Math.log(2);
            int totalFloor = (int)Math.ceil(d);*/
        //计算树一共有多少层
        int totalFloor = calcFloor(size + 1);

        int tmpCurrFloor = -1;
        for (int i = 1; i < size + 1; i++) {
            //计算当前元素所在的层次
            int currFloor = calcFloor(i + 1);

            //如果是新的层次，那么输出换行符
            if (tmpCurrFloor == -1 || tmpCurrFloor != currFloor){
                if(tmpCurrFloor != -1){
                    System.out.println("\r\n");
                }
                tmpCurrFloor = currFloor;
            }

            //输出新行前的tab
            //1.如果是新的行，那么输出行前tab
            //2.tab的数量是  2的（总行数 - 当前行）次方 -1
            if (Math.pow(2,currFloor - 1) ==  i){
                double size = Math.pow(2, totalFloor - currFloor) - 1;
                for (int j = 0 ; j < size ; j++)
                    System.out.print("\t");

            }
            //输出元素
            System.out.print(value[i]);

            //输出当前行应该输出的分隔tab数，tab的数量是  2的(总行数 - 当前行 +1)次方个
            for (int j = 0; j < Math.pow(2,totalFloor - currFloor +1); j++) {
                System.out.print("\t");
            }

        }
        System.out.println();
    }

}
